ArrayList 源码分析

常量与重要的成员变量

// 默认容量
private static final int DEFAULT_CAPACITY = 10;

// 空数组-对应第一个构造函数
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认空数组-对应第二个构造函数。这个与上面EMPTY_ELEMENTDATA要进行区别，根据源码解释说到，两个变量决定了当第一次插入数据时容器的扩容机制，在这里相当于起到了标志位的作用。实际操作看扩容与缩容部分
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// ArrayList内部的真实容器(数组)
transient Object[] elementData;

// ArrayList内部的记录实际装载数据个数
private int size;

构造函数

// 根据用户自定义容量初始化容器
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 默认构造函数
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 由一组数组进行容器的初始化(前提该数组必须是实现了Collection接口，并继承或来源于<E>)
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 倘若返回的Class类型并非Object[]，需要Arrays.copy()将其类型转化为Object[]
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 若该组数组为空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

在EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA两个标志位，个人认为：

• 如果以默认的构造函数模式初始化ArrayList，则以ArrayList内部的增长模式扩展，即初始化时容器大小就是DEFAULT_CAPACITY，即为10
• 如果

增加操作 —— add()

// 顺序插入数据
public boolean add(E e) {
  	// 无论是哪种插入操作，都需要提前进行扩容，防止抛出ArrayIndexOutOfBoundsException
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

// 在指定位置上插入数据
public void add(int index, E element) {
  	// if (index<0 || index>size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);
  	// System.arraycopy(Object src, int srcPos,
  	//					Object dest, int destPos,
  	//					int length)
  	// 即从原数组(src)中的指定位置(src)，复制一定长度的数据(length)，到目标数组(dest)的指定位置上(destPos)
  	System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

// 顺序插入一组数据
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

// 在指定位置上，插入一组数据
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);

  	// 原数组中需要移动的个数
    int numMoved = size - index;
    if (numMoved > 0)
      System.arraycopy(elementData, index, elementData, index + numNew,
                       numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

在ArrayList内部，数组的移动往往通过System.arraycopy()和Array.copy()进行操作。这种方式增加了提高了内聚性，也避免了大量的重复代码出现在不同地方中。

扩容与缩容操作 - ensureCapacity()与trimToSize()

扩容

// 方法域为public，即该方法是方便用户根据自己的需求直接扩展容器容量
public void ensureCapacity(int minCapacity) {
  	// 此时出现了DEFAULTCAPACITY_EMPTY_ELEMENTDATA标志，该字段是表明不同的标志位所要求的最低扩展阈值不同
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        ? 0
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
      	// 最终调用内部的ensureCapacityInternal()
        ensureExplicitCapacity(minCapacity);
    }
}

// 方法域为private，内部只存在简单的判断逻辑，用于判断该数组是不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

// 最终确认容器是否有必要进行扩容操作(毕竟每扩容一次，代表这一次性能消耗，扩容操作越频繁，性能消耗越大)
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
  
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 实际执行扩容操作
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 新容器大小为旧容器的1.5倍
    if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

缩容

// 由于ArrayList本身是不会进行缩容的，于是在进行大量的数据插入删除后，会造成大面积的空间浪费
// 此时用户可以自己通过trimToSize()来缩容
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

删除操作 - remove()

// 在指定位置上删除数据
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
      	// 数组直接向左移动ß
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // 进行清空操作，方便GC回收

    return oldValue;
}

// 删除指定数据(碰到的第一个)
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
      	System.arraycopy(elementData, index+1, elementData, index,
                       numMoved);
    elementData[--size] = null;
}

// 还存在其他删除操作，但原理基本相同

查找操作 - get()

// 时间复杂度O(1)
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

修改操作 - set()

// 时间复杂度O(1)
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

三种遍历ArrayList的方式

// 第一种，通过迭代器遍历
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

// 第二种，随机访问(RandomAccess)，通过索引值去遍历 -> 效率最高
Integer value = null;
int size = list.size();
for (int i = 0; i < size; i++) {
    value = (Integer) list.get(i);        
}

// 第三种，for循环遍历 -> 效率最低
Integer value = null;
for (Integer integer: list) {
    value = integer;
}

---

参考资料：

Java集合干货系列-（一）ArrayList源码解析